Masala #0328

Sizga N ta elementdan iborat binar massiv berilgan(ya’ni massiv elementlari faqatgina 0 va 1 lardan iborat). Siz massivni shunday 3 qism massivga ajratingki har bir qismni alohida o’nlik sanoq tizimiga o’girilganda uchchala qiymat ham bir xil bo’lsin.

Agar massivni yuqoridagi shart asosida uch qismga ajratishning imkoni bo’lsa shu qismlarning 10 lik sanoq tizimidagi qiymatini 10⁹+7 ga bo’lgandagi qoldiqni chop eting, aks holda -1 ni

Eslatma: bu yerda ikkilikdan o’nlik sanoq tizimiga o’girish standart holda bajariladi, ya’ni ikkilikdagi 1010 soni o’nlikda 10 ga teng(5 ga emas).

Kirish faylining dastlabki satrida bitta butun son, T(1 ≤ T ≤ 10) testlar soni kiritiladi.

Har bir test uchun dastlabki qatorda bitta butun son, N(1 ≤ N ≤ 10⁵) to’plam elementlari soni kiritiladi, keyingi satrda N ta binar son {0, 1}, to’plam elementlari kiritiladi.

Chiqish faylida har bir test uchun alohida qatorda bitta butun son, masala shartida so’ralgan javobni chop eting!